/* 继承二叉搜索树 */

import { BinarySearchTree as BSTree } from "./00_二叉搜索树";
import { AVLTreeNode } from "./03_AVL树节点封装_左旋转";

class AVLTree<T> extends BSTree<T> {
  //覆盖父类方法
  protected createNode(value: T): AVLTreeNode<T> {
    return new AVLTreeNode(value);
  }

  /**
   * 根据不平衡的节点的情况（LL/RR/LR/RL）让子树平衡
   * @param root 找到的不平衡点
   */
  rebalanced(root: AVLTreeNode<T>) {
    const pivot = root.higherChild;
    const current = pivot?.higherChild;

    let resultNode: AVLTreeNode<T> | null = null;

    if (pivot?.isLeft) {
      //L
      if (current?.isLeft) {
        resultNode = root.rightRotation();
      } else {
        //R
        current?.leftRotation();
        resultNode = root.rightRotation();
      }
    } else {
      //R
      if (current?.isLeft) {
        //L
        pivot?.rightRotation();
        resultNode = current.leftRotation();
      } else {
        //R
        resultNode = root.leftRotation();
      }
    }

    if (!resultNode?.parent) {
      this.root = resultNode;
    }
  }
}

const avlTree = new AVLTree<number>();

avlTree.insert(50);
avlTree.insert(100);
avlTree.insert(120);
avlTree.insert(150);
avlTree.insert(180);

avlTree.print();
